//如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的： 
//
// 
// n >= 3 
// 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2} 
// 
//
// 给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。 
//
// （回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 
//是 [3, 4, 5, 6, 7, 8] 的一个子序列） 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入: arr = [1,2,3,4,5,6,7,8]
//输出: 5
//解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
// 
//
// 示例 2： 
//
// 
//输入: arr = [1,3,7,11,12,14,18]
//输出: 3
//解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。
// 
//
// 
//
// 提示： 
//
// 
// 3 <= arr.length <= 1000 
// 1 <= arr[i] < arr[i + 1] <= 10^9 
// 
//
// 
//
// 
// 注意：本题与主站 873 题相同： https://leetcode-cn.com/problems/length-of-longest-
//fibonacci-subsequence/ 
//
// Related Topics 数组 哈希表 动态规划 👍 90 👎 0


package LeetCode.editor.cn;


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author ldltd
 * @date 2025-03-31 16:21:52
 * @description LCR 093.最长的斐波那契子序列的长度
 
 */
 
public class Q91FMA {
    public static void main(String[] args) {
    //测试代码
    Q91FMA fun = new Q91FMA();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /*
        * 定义dp[i][j]表示以i,j为最后结尾的斐波那契子序列的最大长度
        * 他们的前一个位置k  ar[j]-ar[i]=x, 如果x存在，且该数字小于ar[i],则是一个合法序列
        * 一个合法的子序列至少有3个元素
        * 因此dp[i][j]= (0,max(dp[k][i]+1,3)
        * */
    public int lenLongestFibSubseq(int[] arr) {
        Map<Integer,Integer> map=new HashMap<>();
        int res=0;
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            map.put(arr[i],i);
        }
        int [][]dp=new int[len][len];
        for (int j = 0; j < len; j++) {
            for (int i = j-1; i >=0&&arr[i]*2>arr[j]; i--) {
                int k=map.getOrDefault(arr[j]-arr[i],-1);
                if(k>=0){
                    dp[i][j]=Math.max(dp[k][i]+1,3);
                }
                res=Math.max(res,dp[i][j]);
            }
        }
        return res;
    }

    public int lenLongestFibSubseq1(int[] arr) {
        int n = arr.length, max = 0;
        int[][] dp = new int[n][n];
        for(int i = 2 ; i < n ; i++){
            //从第三个位置开始，遍历左边的两个位置 j ,k
            int j = 0, k = i-1;
            while(j < k){
                //如果构成了一个合法的序列
                if(arr[j] + arr[k] == arr[i]){
                    //如果j+k目前是0，则 j k i组成一个新序列
                    if(dp[j][k] == 0){
                        dp[k][i] = 3;
                    }else{
                        //否则 当前位置是两个位置+1和当前位置的最大值
                        dp[k][i] = Math.max(dp[j][k]+1, dp[k][i]);
                    }
                    //因为不是每个位置都会用到，因此每次有合法序列都要记录答案
                    max = Math.max(max, dp[k][i]);
                    //继续缩减左边两个指针
                    j++;k--;
                }
                //因为序列递增，如果和小了，收缩左区间
                else if(arr[j] + arr[k] < arr[i]){
                    j++;
                    //否则收缩右区间
                }else {
                    k--;
                }
            }
        }
        return max;
    }



}
//leetcode submit region end(Prohibit modification and deletion)

}
